package pacman.entries.pacman;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;

import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.SimpleDirectedWeightedGraph;

import pacman.controllers.Controller;
import pacman.game.Constants.DM;
import pacman.game.Constants.GHOST;
import pacman.game.Constants.MOVE;
import pacman.game.Game;
//import org.jgrapht.traverse.BreadthFirstIterator;

// 
final class Junction {
	private int node;
	private Junction up;
	private Junction down;
	private Junction left;
	private Junction right;
	private boolean visited;
	private double bfsWeight;
	private Junction bfsParent;
	private int bfsLevel;

	public Junction() {
		node = -1;
		up = null;
		down = null;
		left = null;
		right = null;
		visited = false;
		bfsWeight = 0;
		bfsParent = null;
		bfsLevel = 0;
	}

	public Junction(int n) {
		node = n;
		up = null;
		down = null;
		left = null;
		right = null;
		visited = false;
		bfsWeight = 0;
		bfsParent = null;
		bfsLevel = 0;
	}

	public int getNode() {
		return node;
	}

	public void setNode(int n) {
		node = n;
	}

	public boolean getVisited() {
		return visited;
	}

	public void setVisited(boolean vis) {
		visited = vis;
	}

	public double getBfsWeight() {
		return bfsWeight;
	}

	public void setBfsParent(Junction p) {
		bfsParent = p;
	}

	public Junction getBfsParent() {
		return bfsParent;
	}

	public void setBfsWeight(double bfsW) {
		bfsWeight = bfsW;
	}

	public int getBfsLevel() {
		return bfsLevel;
	}

	public void setBfsLevel(int level) {
		bfsLevel = level;
	}

	public Junction getUp() {
		return up;
	}

	public Junction getDown() {
		return down;
	}

	public Junction getLeft() {
		return left;
	}

	public Junction getRight() {
		return right;
	}

	public void addUp(Junction j) {
		up = j;
	}

	public void addDown(Junction j) {
		down = j;
	}

	public void addLeft(Junction j) {
		left = j;
	}

	public void addRight(Junction j) {
		right = j;
	}

	public boolean equals(Object o) {
		// only look at node, not arraylist of neighbors
		Junction j = (Junction) o;
		return node == j.getNode();
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("Junction Index : " + node + "\n");
		if (up != null)
			sb.append("UP: " + up.getNode() + "\n");
		if (down != null)
			sb.append("Down: " + down.getNode() + "\n");
		if (left != null)
			sb.append("Left: " + left.getNode() + "\n");
		if (right != null)
			sb.append("Right: " + right.getNode() + "\n");

		return sb.toString();
	}
}

/*
 * This is the class you need to modify for your entry. In particular, you need
 * to fill in the getAction() method. Any additional classes you write should
 * either be placed in this package or sub-packages (e.g.,
 * game.entries.pacman.mypackage).
 */
public class HRTPacMan extends Controller<MOVE> {
	private Random rnd = new Random();
	private MOVE[] allMoves = MOVE.values();
	// private int[] node = null;// array of node indices that the game returns
	private ArrayList<Junction> nodeSet;// arraylist of nodes that we create

	// Arranging Junction over all nodes of Game graph(not our graph), Easy to
	// find things by integer index.
	private int[] totalNode;

	// Arranging Junctions object over all the nodes of Game graph(not our
	// graph), Easy to find things by integer index
	private Junction[] totalJunction;
	// from the array "node"
	private SimpleDirectedWeightedGraph<Junction, DefaultWeightedEdge> graph;// graph
																				// that
																				// we
																				// create
	// private BreadthFirstIterator<Junction, DefaultWeightedEdge> bfs;

	private float[] itemWeight;// the weights that we assign to pills, power
								// pills, inedible ghosts, edible ghosts, etc.

	public HRTPacMan() {
		nodeSet = new ArrayList<Junction>();

		itemWeight = new float[4];
		itemWeight[0] = 10;
		itemWeight[1] = 50;
		itemWeight[2] = 100;
		itemWeight[3] = 500;

		// for (int i = 0; i < 4; i++) {
		// itemWeight[i] = rnd.nextFloat();
		// }

		// create the graph
		graph = new SimpleDirectedWeightedGraph<Junction, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
	}

	//Not Using this Method. 
	public MOVE getMove(Game game, long timeDue) {
		// Dont Use this function Anymore
		/*
		 * // if we are at the beginning of the level if
		 * (game.getCurrentLevelTime() == 0) { createJunctionGraph(game); }
		 * int[] coefficient = { 10, 100, 200, 200 };
		 * 
		 * int pacmanNode = game.getPacmanCurrentNodeIndex(); //
		 * System.out.println("Present Pacman location: " + pacmanNode);
		 * Junction nodeJunction = getNodeEdges(pacmanNode, nodeSet, game);
		 * 
		 * // // check for replicated junctions // ArrayList<Junction>
		 * PacMacNodes = new ArrayList<Junction>(); // if(nodeJunction.getLeft()
		 * != null) // PacMacNodes.add(nodeJunction.getLeft()); //
		 * if(nodeJunction.getRight() != null) //
		 * PacMacNodes.add(nodeJunction.getRight()); //
		 * if(nodeJunction.getDown() != null) //
		 * PacMacNodes.add(nodeJunction.getDown()); // if(nodeJunction.getUp()
		 * != null) // PacMacNodes.add(nodeJunction.getUp()); // // for(int i =
		 * 0; i < PacMacNodes.size(); i++) // for(int j = i+1; j <
		 * PacMacNodes.size(); j++){ // Junction j1 =
		 * (Junction)PacMacNodes.get(i); // Junction j2 =
		 * (Junction)PacMacNodes.get(j); // if(j1 != null && j2 != null &&
		 * j1.equals(j2)) // j2 = null; // }
		 * 
		 * // Do BFS over the graph from node of the PacMan
		 * 
		 * // reset visited variable for all junctions Iterator<Junction>
		 * iterator = nodeSet.iterator(); while (iterator.hasNext()) {
		 * (iterator.next()).setVisited(false); }
		 * 
		 * // run BFS in PacMan node as root MOVE nextMove = bfs(nodeJunction,
		 * 0, game);
		 * 
		 * // System.out.println(nodeJunction.toString());
		 * 
		 * System.out.println("----- Node: " + nodeJunction.getNode()); Junction
		 * destJ; destJ = nodeJunction.getRight(); if (destJ != null)
		 * System.out.println(destJ.getNode() + " Right = " +
		 * getEdgeWeight(nodeJunction, destJ, game)); destJ =
		 * nodeJunction.getLeft(); if (destJ != null)
		 * System.out.println(destJ.getNode() + " Left  = " +
		 * getEdgeWeight(nodeJunction, destJ, game)); destJ =
		 * nodeJunction.getDown(); if (destJ != null)
		 * System.out.println(destJ.getNode() + " Down  = " +
		 * getEdgeWeight(nodeJunction, destJ, game)); destJ =
		 * nodeJunction.getUp(); if (destJ != null)
		 * System.out.println(destJ.getNode() + " Up    = " +
		 * getEdgeWeight(nodeJunction, destJ, game));
		 * 
		 * System.out.println(nextMove); return nextMove; // until we get our
		 * algorithm working, make a random move // return
		 * allMoves[rnd.nextInt(allMoves.length)];
		 */
		return null;
	}

	@Override
	public MOVE getMove(Game game, long timeDue, int[] coefficient) {
		// if we are at the beginning of the level
		if (game.getCurrentLevelTime() == 0) {
			// createJunctionGraph(game);// We are not using it

			createJunctionGraphNew(game);
//			for (Junction junction : graph.vertexSet()) {
//				System.out.print("Junction " + junction.getNode() + ": ");
//				System.out.println(graph.edgesOf(junction).size());
//			}
		}
		itemWeight[0] = coefficient[0];
		itemWeight[1] = coefficient[1];
		itemWeight[2] = coefficient[2];
		itemWeight[3] = coefficient[3];
		
		// int[] coefficient = {10, 100, 200, 200};
		// for(int cof: coefficient) System.out.println("Weight" + cof);
		int pacmanNode = game.getPacmanCurrentNodeIndex();
		// System.out.println("Present Pacman location: " + pacmanNode);
		Junction nodeJunction = getNodeEdgesNew(pacmanNode, nodeSet, game);
		
		/*
		 * This is Greedy Approach for the PacMan
		 */
//		
//		double max = 0.0;
//		MOVE next = MOVE.NEUTRAL;
//		if(nodeJunction.getDown() != null){
//			double weight = getEdgeWeight(nodeJunction, nodeJunction.getDown(), game);
//			if(weight >= max){
//				max = weight;
//				next = MOVE.DOWN;
//				//next = game.getNextMoveTowardsTarget(nodeJunction.getNode(), nodeJunction.getDown().getNode(), DM.PATH);
//			}
//		}
//		if(nodeJunction.getUp() != null){
//			double weight = getEdgeWeight(nodeJunction, nodeJunction.getUp(), game);
//			if(weight >= max){
//				max = weight;
//				next = MOVE.UP;
//			}
//		}
//		if(nodeJunction.getRight() != null){
//			double weight = getEdgeWeight(nodeJunction, nodeJunction.getRight(), game);
//			if(weight >= max){
//				max = weight;
//				next = MOVE.RIGHT;
//			}
//		}
//		if(nodeJunction.getLeft() != null){
//			double weight = getEdgeWeight(nodeJunction, nodeJunction.getLeft(), game);
//			if(weight >= max){
//				max = weight;
//				next = MOVE.LEFT;
//			}
//		}
		
		//System.out.println(nodeJunction.toString());

		// Hamid-----------------
		// Do BFS over the graph from node of the PacMan

		// reset visited variable for all junctions
		Iterator<Junction> iterator = nodeSet.iterator();
		while (iterator.hasNext()) {
			Junction Junct = iterator.next();
			Junct.setVisited(false);
			Junct.setBfsLevel(0);
			Junct.setBfsParent(null);
			Junct.setBfsWeight(0);
		}

		// run BFS in PacMan node as root
		MOVE nextMove = bfs(nodeJunction, 0, game);
		
		// random move if the nextMove is null and previous move is not possible
		if(nextMove == null){
			MOVE[] pMoves = game.getPossibleMoves(nodeJunction.getNode());
			for (int k = 0; k < pMoves.length; k++)
				if(game.getPacmanLastMoveMade() == pMoves[k])
					nextMove = pMoves[k];
			if(nextMove==null)
				nextMove = pMoves[rnd.nextInt(pMoves.length)];
		}
		// System.out.println(nodeJunction.toString());

//		System.out.println("----- Node: " + nodeJunction.getNode());
//		Junction destJ;
//		destJ = nodeJunction.getRight();
//		if (destJ != null)
//			System.out.println(destJ.getNode() + " Right = "
//					+ getEdgeWeight(nodeJunction, destJ, game));
//		destJ = nodeJunction.getLeft();
//		if (destJ != null)
//			System.out.println(destJ.getNode() + " Left  = "
//					+ getEdgeWeight(nodeJunction, destJ, game));
//		destJ = nodeJunction.getDown();
//		if (destJ != null)
//			System.out.println(destJ.getNode() + " Down  = "
//					+ getEdgeWeight(nodeJunction, destJ, game));
//		destJ = nodeJunction.getUp();
//		if (destJ != null)
//			System.out.println(destJ.getNode() + " Up    = "
//					+ getEdgeWeight(nodeJunction, destJ, game));
		//System.out.println(nextMove);
		
		
		
		return nextMove;
		//System.out.println(next);
		//return next;
		// if(nodeJunction.getLeft() != null)
		// System.out.println(getEdgeWeight(coefficient, nodeJunction,
		// nodeJunction.getLeft(), game));
		// until we get our algorithm working, make a random move
		// return allMoves[rnd.nextInt(allMoves.length)];
	}

	// By Taranjeet----- For personal use only--
	private void createJunctionGraphNew(Game game) {
		graph = new SimpleDirectedWeightedGraph<Junction, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		ArrayList<Integer> junctionList = new ArrayList<>();
		// int[] node = game.getJunctionIndices();
		for (int n : game.getJunctionIndices()) {
			junctionList.add(n);
		}
		for (int n : game.getPowerPillIndices()) {
			junctionList.add(n);
		}
		// int[] powerpills = game.getPowerPillIndices();
		Collections.sort(junctionList);
//		 System.out.println(junctionList.size());
		//System.out.println(junctionList.toString());
		totalNode = new int[game.getNumberOfNodes()];
		totalJunction = new Junction[totalNode.length];

		// add the nodes
		for (int n = 0; n < junctionList.size(); n++) {
			Junction junct = new Junction(junctionList.get(n));
			graph.addVertex(junct);
			nodeSet.add(junct);
			totalNode[junct.getNode()] = junct.getNode();
			totalJunction[junct.getNode()] = junct;
		}
		// System.out.println();
		int junctionNode = -1;
		for (Junction j : nodeSet) {
			MOVE[] move = game.getPossibleMoves(j.getNode());
			for (MOVE mv : move) {
				junctionNode = walk(j.getNode(), mv, game, totalNode);
				if (mv == MOVE.UP)
					j.addUp(totalJunction[junctionNode]);
				if (mv == MOVE.DOWN)
					j.addDown(totalJunction[junctionNode]);
				if (mv == MOVE.LEFT)
					j.addLeft(totalJunction[junctionNode]);
				if (mv == MOVE.RIGHT)
					j.addRight(totalJunction[junctionNode]);

				//Look out for this statement
				//Without iff, it was saying no such vertex in graph, which is weird as 
				//all the vertices added already before.
				if(graph.containsVertex(j) && graph.containsVertex(totalJunction[junctionNode]))
					graph.addEdge(j, totalJunction[junctionNode]);

			}
//			 System.out.println(j.toString());
		}

	}

	public Junction getNodeEdgesNew(int nodeIndex,
			ArrayList<Junction> junctions, Game game) {
		int junctionNode = -1;
		if (totalNode[nodeIndex] > 0) {
			return totalJunction[nodeIndex];
		}
		Junction nodeJunction = new Junction(nodeIndex);
		MOVE[] move = game.getPossibleMoves(nodeIndex);
		for (MOVE mv : move) {
			junctionNode = walk(nodeIndex, mv, game, totalNode);
			if (mv == MOVE.UP)
				nodeJunction.addUp(totalJunction[junctionNode]);
			if (mv == MOVE.DOWN)
				nodeJunction.addDown(totalJunction[junctionNode]);
			if (mv == MOVE.LEFT)
				nodeJunction.addLeft(totalJunction[junctionNode]);
			if (mv == MOVE.RIGHT)
				nodeJunction.addRight(totalJunction[junctionNode]);

		}
		return nodeJunction;
	}

	private int walk(int node, MOVE move, Game game, int[] junctions) {
		int nextNode = game.getNeighbour(node, move);
		int junctionNode = 0;
		if (junctions[nextNode] > 0)
			return nextNode;

		MOVE[] moveNext = game.getPossibleMoves(nextNode);
		for (MOVE mv : moveNext) {
			if (mv == move.opposite())
				continue;
			junctionNode = walk(nextNode, mv, game, junctions);
		}
		return junctionNode;
	}

	//Not Using this function
	private void createJunctionGraph(Game game) {

		//Created By Ryan -- Not Using it any more.
		/*
		graph = new SimpleDirectedWeightedGraph<Junction, DefaultWeightedEdge>(
				DefaultWeightedEdge.class);
		ArrayList<Integer> junctionList = new ArrayList<>();
		// int[] node = game.getJunctionIndices();
		for (int n : game.getJunctionIndices()) {
			junctionList.add(n);
		}
		for (int n : game.getPowerPillIndices()) {
			junctionList.add(n);
		}

		// int[] powerpills = game.getPowerPillIndices();
		Collections.sort(junctionList);
		// System.out.println(junctionList.size());
		System.out.println(junctionList.toString());

		// add the nodes
		for (int n = 0; n < junctionList.size(); n++) {
			Junction junct = new Junction(junctionList.get(n));
			graph.addVertex(junct);
			nodeSet.add(junct);
		}
		for (final Junction j : graph.vertexSet()) {
			for (final Junction j2 : graph.vertexSet()) {
				if (j.equals(j2)) {
					// no self-references
					continue;
				} else {
					boolean valid = true;

					MOVE[] move = game.getPossibleMoves(j.getNode());
					List<MOVE> moveSet = new ArrayList<MOVE>();
					for (MOVE mv : move) {
						moveSet.add(mv);
					}
					if (moveSet.contains(MOVE.UP)) {
						int[] up = game.getShortestPath(j.getNode(),
								j2.getNode(), MOVE.UP);
						// check if path passes through other nodes
						for (int i = 0; i < (up.length - 1); i++) {
							Junction temp = new Junction(up[i]);
							if (nodeSet.contains(temp)) {
								valid = false;
								break;
							}
						}
						// if path does not pass through other nodes
						if (valid) {
							graph.addEdge(j, j2);
							j.addUp(j2);
						}
					}

					if (moveSet.contains(MOVE.DOWN)) {
						valid = true;
						int[] down = game.getShortestPath(j.getNode(),
								j2.getNode(), MOVE.DOWN);

						// check if path passes through other nodes
						for (int i = 0; i < (down.length - 1); i++) {
							if (nodeSet.contains(new Junction(down[i]))) {
								valid = false;
								break;
							}
						}
						// if path does not pass through other nodes
						if (valid) {
							graph.addEdge(j, j2);
							j.addDown(j2);
						}
					}

					if (moveSet.contains(MOVE.LEFT)) {
						valid = true;
						int[] left = game.getShortestPath(j.getNode(),
								j2.getNode(), MOVE.LEFT);
						// check if path passes through other nodes
						for (int i = 0; i < (left.length - 1); i++) {
							if (nodeSet.contains(new Junction(left[i]))) {
								valid = false;
								break;
							}
						}
						// if path does not pass through other nodes
						if (valid) {
							graph.addEdge(j, j2);
							j.addLeft(j2);
						}
					}

					if (moveSet.contains(MOVE.LEFT)) {
						valid = true;
						int[] right = game.getShortestPath(j.getNode(),
								j2.getNode(), MOVE.RIGHT);
						// check if path passes through other nodes
						for (int i = 0; i < (right.length - 1); i++) {
							if (nodeSet.contains(new Junction(right[i]))) {
								valid = false;
								break;
							}
						}
						// if path does not pass through other nodes
						if (valid) {
							graph.addEdge(j, j2);
							j.addRight(j2);
						}
					}

				}
			}
		}
		*/
	}

	//Not Using this function
	public Junction isValidJunction(ArrayList<Junction> junctions,
			int nodeIndex, Game game, MOVE mv) {
		/*Iterator<Junction> iterator = junctions.iterator();
		while (iterator.hasNext()) {
			Junction j2 = iterator.next();

			if (nodeIndex == j2.getNode()) {
				return j2;
			} else {
				boolean valid = true;

				int[] left = game.getShortestPath(nodeIndex, j2.getNode(), mv);
				// check if path passes through other nodes
				for (int i = 0; i < (left.length - 1); i++) {
					Junction temp = new Junction(left[i]);
					if (junctions.contains(temp)) {
						valid = false;
						break;
					}
				}
				// if path does not pass through other nodes
				if (valid) {
					// pacman.graph.addEdge(j, j2);
					return j2;
				}

			}

		}*/
		return null;
	}

	//Not Using this function
	public Junction getNodeEdges(int nodeIndex, ArrayList<Junction> junctions,
			Game game) {
		/*Junction nodeJunction = new Junction(nodeIndex);

		MOVE[] move = game.getPossibleMoves(nodeIndex);
		for (MOVE mv : move) {
			if (mv == MOVE.LEFT) {
				nodeJunction.addLeft(isValidJunction(junctions, nodeIndex,
						game, mv));
			} else if (mv == MOVE.RIGHT) {
				nodeJunction.addRight(isValidJunction(junctions, nodeIndex,
						game, mv));
			} else if (mv == MOVE.UP) {
				nodeJunction.addUp(isValidJunction(junctions, nodeIndex, game,
						mv));
			} else if (mv == MOVE.DOWN) {
				nodeJunction.addDown(isValidJunction(junctions, nodeIndex,
						game, mv));
			}
		}

		return nodeJunction;*/
		
		return null;
	}

	public double getEdgeWeight(Junction source, Junction destination, Game game) {
		int[] path = game.getShortestPath(source.getNode(),
				destination.getNode());
		int pills = 0, powerpills = 0, ghost = 0, edibleGhost = 0;
		for (int node : path) {
			if (game.getPillIndex(node) != -1)
				if(game.isPillStillAvailable(game.getPillIndex(node))) 
					pills++;
						
			if (game.getPowerPillIndex(node) != -1)
				if(game.isPowerPillStillAvailable(game.getPowerPillIndex(node)))
					powerpills++;
			
			
			if (game.getGhostCurrentNodeIndex(GHOST.BLINKY) == node)
				if (game.isGhostEdible(GHOST.BLINKY))edibleGhost++;
				else ghost++;
			if (game.getGhostCurrentNodeIndex(GHOST.INKY) == node)
				if (game.isGhostEdible(GHOST.INKY))edibleGhost++;
				else ghost++;
			if (game.getGhostCurrentNodeIndex(GHOST.PINKY) == node)
				if (game.isGhostEdible(GHOST.PINKY)) edibleGhost++;
				else ghost++;
			if (game.getGhostCurrentNodeIndex(GHOST.SUE) == node)
				if (game.isGhostEdible(GHOST.SUE)) edibleGhost++;
				else ghost++;

		}
		double weight = 0.0;
		// System.out.println("Total Pills: "+ pills);
		// System.out.println("Total PowerPills: "+ powerpills);
		// System.out.println("Total ghost: "+ ghost);
		// System.out.println("Total Edible Ghost: "+ edibleGhost);

		weight = itemWeight[0] * pills + itemWeight[1] * powerpills
				+ itemWeight[2] * edibleGhost - itemWeight[3] * ghost;
//		weight += rnd.nextDouble();
		return weight;
	}

	public MOVE bfs(Junction root, int level, Game game) {
		int maxLevel = 5;
		MOVE nextMove = null;

		Queue<Junction> bfsTree = new LinkedList<Junction>();

		root.setVisited(true);
		if (root.getUp() != null) {
			(root.getUp()).setBfsParent(root);
			(root.getUp()).setBfsLevel(root.getBfsLevel() + 1);
			(root.getUp()).setVisited(true);
			bfsTree.add(root.getUp());
		}
		if (root.getDown() != null) {
			(root.getDown()).setBfsParent(root);
			(root.getDown()).setBfsLevel(root.getBfsLevel() + 1);
			(root.getDown()).setVisited(true);
			bfsTree.add(root.getDown());
		}
		if (root.getLeft() != null) {
			(root.getLeft()).setBfsParent(root);
			(root.getLeft()).setBfsLevel(root.getBfsLevel() + 1);
			(root.getLeft()).setVisited(true);
			bfsTree.add(root.getLeft());
		}
		if (root.getRight() != null) {
			(root.getRight()).setBfsParent(root);
			(root.getRight()).setBfsLevel(root.getBfsLevel() + 1);
			(root.getRight()).setVisited(true);
			bfsTree.add(root.getRight());
		}

		double maxWeight = -100000;
		double maxBfsLevel = 0;
		Junction maxJunction = null;
		while (bfsTree.size() > 0) {
			Junction nextJunc = (Junction) bfsTree.remove();
			Junction parentJunc = nextJunc.getBfsParent();

			if (true) {
				nextJunc.setBfsWeight(parentJunc.getBfsWeight()
						+ getEdgeWeight(parentJunc, nextJunc, game));
				
//				System.out.println("parent: " + parentJunc.getNode() +
//									"\tchild: " + nextJunc.getNode() +
//									"\tchild level: " + nextJunc.getBfsLevel() +
//									"\tchildBFSW: " + nextJunc.getBfsWeight());
				
				if (nextJunc.getBfsWeight() == maxWeight && maxBfsLevel == maxLevel)
					return null;
				
				if (nextJunc.getBfsWeight() >= maxWeight) {
					maxWeight = nextJunc.getBfsWeight();
					maxBfsLevel = nextJunc.getBfsLevel();
					maxJunction = nextJunc;
				}

				if (nextJunc.getBfsLevel() < maxLevel) {
					if (nextJunc.getUp() != null
							&& !(nextJunc.getUp()).getVisited()) {
						(nextJunc.getUp()).setBfsParent(nextJunc);
						(nextJunc.getUp()).setBfsLevel(nextJunc.getBfsLevel() + 1);
						(nextJunc.getUp()).setVisited(true);
						bfsTree.add(nextJunc.getUp());
					}
					if (nextJunc.getDown() != null
							&& !(nextJunc.getDown()).getVisited()) {
						(nextJunc.getDown()).setBfsParent(nextJunc);
						(nextJunc.getDown()).setBfsLevel(nextJunc.getBfsLevel() + 1);
						(nextJunc.getDown()).setVisited(true);
						bfsTree.add(nextJunc.getDown());
					}
					if (nextJunc.getLeft() != null
							&& !(nextJunc.getLeft()).getVisited()) {
						(nextJunc.getLeft()).setBfsParent(nextJunc);
						(nextJunc.getLeft()).setBfsLevel(nextJunc.getBfsLevel() + 1);
						(nextJunc.getLeft()).setVisited(true);
						bfsTree.add(nextJunc.getLeft());
					}
					if (nextJunc.getRight() != null
							&& !(nextJunc.getRight()).getVisited()) {
						(nextJunc.getRight()).setBfsParent(nextJunc);
						(nextJunc.getRight()).setBfsLevel(nextJunc.getBfsLevel() + 1);
						(nextJunc.getRight()).setVisited(true);
						bfsTree.add(nextJunc.getRight());
					}
				}
			}
		}

		Junction parentJunction = maxJunction.getBfsParent();
		Junction childJunction = maxJunction;

		while ((childJunction.getBfsParent()).getBfsLevel() > 0) {
			childJunction = parentJunction;
			parentJunction = childJunction.getBfsParent();
		}

		if (parentJunction.getUp() != null
				&& (parentJunction.getUp()).equals(childJunction))
			nextMove = MOVE.UP;
		else if (parentJunction.getDown() != null
				&& (parentJunction.getDown()).equals(childJunction))
			nextMove = MOVE.DOWN;
		else if (parentJunction.getLeft() != null
				&& (parentJunction.getLeft()).equals(childJunction))
			nextMove = MOVE.LEFT;
		else if (parentJunction.getRight() != null
				&& (parentJunction.getRight()).equals(childJunction))
			nextMove = MOVE.RIGHT;


		//System.out.println( "Next move node#: " + childJunction.getNode() + "  move: " + nextMove);

		return nextMove;
	}
	
	public double findMax(double[] numbers) {
		double largest = numbers[0];
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] > largest) {
				largest = numbers[i];
			}
		}
		return largest;
	}

}